#include<vector>
#include<queue>
using std::priority_queue;
using std::vector;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct cmp {
    bool operator() (ListNode *a, ListNode *b) {
        // 返回true说明a的优先级低，在堆中排后面
        return a->val >= b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, std::vector<ListNode*>, cmp> heap;
        for (auto n : lists) {
            if (n != nullptr)
                heap.push(n);
        }
        ListNode head;
        auto curPtr = &head;
        while (!heap.empty()) {
            auto p = heap.top();
            curPtr->next = p;
            curPtr = curPtr->next;
            heap.pop();
            if (p->next != nullptr) heap.push(p->next);
        }
        return head.next;
    }
};


